/**
 * 
 */
package combinatorics.passed;

/**
 * @author Michael
 * http://wordaligned.org/articles/next-permutation#tocwhats-happening-here
 */
public class NextPermutation {

	/**
	Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

	If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

	The replacement must be in-place, do not allocate extra memory.

	Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
	1,2,3 → 1,3,2
	3,2,1 → 1,2,3
	1,1,5 → 1,5,1
	 */
	public void nextPermutation(int[] num) {

		int i = num.length - 2;
		// longest monotonically decreasing tail from end side
		for (; i >= 0 && num[i] >= num[i + 1]; i--) {
		}

		if (i >= 0) {
			// find first element (back to front) greater than the last element of head
			int j = num.length - 1;
			while (num[j] <= num[i]) {
				j--;
			}
			swap(num, i, j);
		}

		reverse(num, i + 1, num.length - 1);

	}

	public static void swap(int[] arr, int i, int j) {
		assert (arr != null);
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	public static void reverse(int[] s, int start, int end) {

		for (; start < end; ++start, --end) {
			int tmp = s[start];
			s[start] = s[end];
			s[end] = tmp;
		}
	}

	public static boolean nextPermutation(char[] s) {
		// if already descending sorted, return false and reverse
		int i = s.length - 2;
		while (i >= 0 && s[i] >= s[i + 1]) {
			--i;
		}
		if (i < 0) {
			reverse(s, 0, s.length - 1);
			return false;
		}

		// from the end of the s, to find the first element that is greater than the pivot
		int j = s.length - 1;
		while (s[j] <= s[i]) {
			--j;
		}

		// swap i and j
		swap(s, i, j);

		// reverse the left side of pivot
		reverse(s, i + 1, s.length - 1);

		return true;
	}

	public static void reverse(char[] s, int start, int end) {
		for (; start < end; ++start, --end) {
			char tmp = s[start];
			s[start] = s[end];
			s[end] = tmp;
		}
	}

	public static void swap(char[] arr, int i, int j) {
		assert (arr != null);
		char tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	/**
	 * 
	 */
	public NextPermutation() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		char[] s = "AAB".toCharArray();
		boolean undone;
		do {
			undone = nextPermutation(s);
			System.out.println(new String(s));
		} while (undone);
	}

}
